#include<iostream>
using namespace std;
#include<vector>
#include<string>
#include<math.h>
#include<cstring>

const int MAX = 20;
class Solution {
public:
    vector<vector<string>> ret;
public:
    vector<vector<string>> solveNQueens(int n) {
        int record[MAX];
        memset(record,0,sizeof(int)*MAX);
        recur(0,record,n);
        return ret;
    }

    void recur(int i,int record[],int n) {
        if(i == n) {
            vector<string> vret;
            for(int i=0; i<n; i++) {
                string svret = "";
                for(int j=0; j<n; j++) {
                    if(j == record[i]) {
                        cout << "1" << " ";
                        svret += 'Q';
                    } else {
                        cout << "0" << " ";
                        svret += '.';
                    }
                }
                vret.push_back(svret);
                cout << endl;
            }
            ret.push_back(vret);
            cout << "=================" << endl;
            return;
        }
        for(int k=0; k<n; k++) {
            if(isValid(i,k,record)) {
                record[i] = k;
                recur(i+1,record,n);
            }
        }
    }

    bool isValid(int x,int y,int record[]) {
        for(int i=0; i<x; i++) {
            if(y == record[i] || abs(x-i) == abs(y-record[i])) {
                return false;
            }
        }
        return true;
    }
};

class Solution1 {
public:
    vector<vector<string>> solveNQueens(int n) {

    }
    void recur(int limit,int col,int left,int right,int record[])
    {
        if(limit == col) {
            return;
        }
        int curLimit = col | left | right;
        while(curLimit) {
            
        }
    }
};
int main() {
    auto ret = Solution().solveNQueens(9);
    for(auto it = ret.begin(); it != ret.end(); it++) {
        vector<string> curSolution = *it;
        for(auto vit = curSolution.begin(); vit != curSolution.end(); vit++) {
            cout << *vit << endl;
        }
        cout << "=============" << endl;
    }
    return 0;
}